package search.doublepointer;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/valid-triangle-number/
 * <p>
 * 有效三角形个数
 */
class ValidTriangleNum {

    public static void main(String[] args) {
        int[] nums = {2, 2, 3, 4};
        System.out.println(new ValidTriangleNum().triangleNumber(nums));
    }

    public int triangleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int total = 0;
        for (int k = nums.length - 1; k >= 2; k--) {
            //固定一边
            int start = 0;
            int end = k - 1;
            while (start < end) {
                if (nums[start] + nums[end] > nums[k]) {
                    total += end - start;
                    end--;
                } else {
                    start++;
                }
            }
        }
        return total;
    }
}

